package com.power.structure.heap;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/6/15 10:19 上午
 */
public class BigHeap {
    int data[];
    public int size = 0;
    private int capacity = 20;

    public BigHeap() {
        data = new int[capacity];
    }

    public int parent(int index) {
        return (index - 1) / 2;
    }

    public int leftChild(int index) {
        return 2 * index + 1;
    }

    public int rightChild(int index) {
        return 2 * index + 2;
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }

    public void add(int element) {
        data[size++] = element;
    }


    public void shift(int i) {
        while (i > 0 && data[i] > data[parent(i)]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    public void enQueue(int element) {
        add(element);
        shift(size - 1);
    }

    public void deque(int index) {
        remove(index);
        down(index);
    }

    public void rangeCheck(int index) {
        if (index > size || index < 0) {
            throw new IllegalStateException("索引越界啦");
        }
    }

    public void remove(int index) {
        data[index] = data[size - 1];
        size--;
    }

    public void down(int i) {
        while (i > 0 && data[i] < data[leftChild(i)] || data[i] < data[rightChild(i)]) {
            //大于左子节点 交换
            if (data[i] > data[leftChild(i)]) {
                swap(i, leftChild(i));
                i = leftChild(i);
            } else {
                swap(i, rightChild(i));
                i = rightChild(i);
            }
        }
    }

    public void swap(int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }

    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(" " + data[i]);
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        BigHeap bigHeap = new BigHeap();
        for (int i = 0; i < 10; i++) {
            bigHeap.enQueue(i);
        }
        bigHeap.display();
        System.out.println("size()::" + bigHeap.size);

        bigHeap.deque(1);
        bigHeap.display();
    }
}
